ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Graph dynamical system</title>

</head>

Graph dynamical system

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Mathematics" title="Mathematics">mathematics</a>, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties (e.g. the network connectivity) and the global dynamics that result.

The work on GDSs considers finite graphs and finite state spaces. As such, the research typically involves techniques from, e.g., <a href="Graph_theory" title="Graph theory">graph theory</a>, <a href="Combinatorics" title="Combinatorics">combinatorics</a>, <a href="Algebra" title="Algebra">algebra</a>, and <a href="Dynamical_systems" class="mw-redirect" title="Dynamical systems">dynamical systems</a> rather than differential geometry. In principle, one could define and study GDSs over an infinite graph (e.g. <a href="Cellular_automata" class="mw-redirect" title="Cellular automata">cellular automata</a> or <a href="Stochastic_cellular_automata" class="mw-redirect" title="Stochastic cellular automata">probabilistic cellular automata</a> over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} ^{k}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} ^{k}}</annotation>

</semantics>

</math><img src="./2804394ff2f7291056f4c050dc1b32809e755bdb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.639ex; height:2.676ex;" alt="{\displaystyle \mathbb {Z} ^{k}}" loading="lazy"> or <a href="Interacting_particle_systems" class="mw-redirect" title="Interacting particle systems">interacting particle systems</a> when some randomness is included), as well as GDSs with infinite state space (e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} }</annotation>

</semantics>

</math><img src="./786849c765da7a84dbc3cce43e96aad58a5868dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {R} }" loading="lazy"> as in coupled map lattices); see, for example, Wu.<a href="#cite_note-wu-05-1">[1]</a> In the following, everything is implicitly assumed to be finite unless stated otherwise.

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

A graph dynamical system is constructed from the following components:

<ul><li>A finite graph Y with vertex set v[Y] = {1,2, ... , n}. Depending on the context the graph can be directed or undirected.</li>

<li>A state xv for each vertex v of Y taken from a finite set K. The system state is the n-tuple x = (x1, x2, ... , xn), and x[v] is the tuple consisting of the states associated to the vertices in the 1-neighborhood of v in Y (in some fixed order).</li>

<li>A vertex function fv for each vertex v. The vertex function maps the state of vertex v at time t to the vertex state at time t + 1 based on the states associated to the 1-neighborhood of v in Y.</li>

<li>An update scheme specifying the mechanism by which the mapping of individual vertex states is carried out so as to induce a discrete dynamical system with map F: Kn → Kn.</li></ul>

</blockquote>

The phase space associated to a dynamical system with map F: Kn → Kn is the finite directed graph with vertex set Kn and directed edges (x, F(x)). The structure of the phase space is governed by the properties of the graph Y, the vertex functions (fi)i, and the update scheme. The research in this area seeks to infer phase space properties based on the structure of the system constituents. The analysis has a local-to-global character.

<div class="mw-heading mw-heading2"><h2 id="Generalized_cellular_automata_(GCA)">Generalized cellular automata (GCA)</h2></div>

If, for example, the update scheme consists of applying the vertex functions synchronously one obtains the class of generalized cellular automata (CA). In this case, the global map F: Kn → Kn is given by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(x)_{v}=f_{v}(x[v])\;.}</annotation>

</semantics>

</math><img src="./1288e0d6c6b1f355e7055762d8b2de758e8208f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.029ex; height:2.843ex;" alt="{\displaystyle F(x)_{v}=f_{v}(x[v])\;.}" loading="lazy">

This class is referred to as generalized cellular automata since the classical or standard <a href="Cellular_automaton" title="Cellular automaton">cellular automata</a> are typically defined and studied over regular graphs or grids, and the vertex functions are typically assumed to be identical.

Example: Let Y be the circle graph on vertices {1,2,3,4} with edges {1,2}, {2,3}, {3,4} and {1,4}, denoted Circ4. Let K = {0,1} be the state space for each vertex and use the function nor3 : K3 → K defined by nor3(x,y,z) = (1 + x)(1 + y)(1 + z) with arithmetic modulo 2 for all vertex functions. Then for example the system state (0,1,0,0) is mapped to (0, 0, 0, 1) using a synchronous update. All the transitions are shown in the phase space below.

<div class="mw-heading mw-heading2"><h2 id="Sequential_dynamical_systems_(SDS)">Sequential dynamical systems (SDS)</h2></div>

If the vertex functions are applied asynchronously in the sequence specified by a word w = (w1, w2, ... , wm) or permutation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy"> = ( <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{1}}</annotation>

</semantics>

</math><img src="./542cbd3dacd0a061d666ed7fc4ed7ad15b47444b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.379ex; height:2.009ex;" alt="{\displaystyle \pi _{1}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{2},\dots ,\pi _{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{2},\dots ,\pi _{n}}</annotation>

</semantics>

</math><img src="./75ccafc3fd6f0d0728c79f152a76f6ad72b5e46b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.101ex; height:2.009ex;" alt="{\displaystyle \pi _{2},\dots ,\pi _{n}}" loading="lazy">) of v[Y] one obtains the class of <a href="Sequential_dynamical_system" title="Sequential dynamical system">Sequential dynamical systems</a> (SDS).<a href="#cite_note-Mortveit-08-2">[2]</a> In this case it is convenient to introduce the Y-local maps Fi constructed from the vertex functions by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;.}</annotation>

</semantics>

</math><img src="./b0297cda06442aa0a2bb3a1835cf94c5e8011fba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:48.041ex; height:2.843ex;" alt="{\displaystyle F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;.}" loading="lazy"></dd></dl>

The SDS map F = [FY , w] : Kn → Kn is the function composition

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;.}</annotation>

</semantics>

</math><img src="./ca42ec3794afcdf858b2c72b17b1c5d18f8c90cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:46.227ex; height:3.176ex;" alt="{\displaystyle [F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;.}" loading="lazy"></dd></dl>

If the update sequence is a permutation one frequently speaks of a permutation SDS to emphasize this point.

Example: Let Y be the circle graph on vertices {1,2,3,4} with edges {1,2}, {2,3}, {3,4} and {1,4}, denoted Circ4. Let K={0,1} be the state space for each vertex and use the function nor3 : K3 → K defined by nor3(x, y, z) = (1 + x)(1 + y)(1 + z) with arithmetic modulo 2 for all vertex functions. Using the update sequence (1,2,3,4) then the system state (0, 1, 0, 0) is mapped to (0, 0, 1, 0). All the system state transitions for this sequential dynamical system are shown in the phase space below.

<div class="mw-heading mw-heading2"><h2 id="Stochastic_graph_dynamical_systems">Stochastic graph dynamical systems</h2></div>

From, e.g., the point of view of applications it is interesting to consider the case where one or more of the components of a GDS contains stochastic elements. Motivating applications could include processes that are not fully understood (e.g. dynamics within a cell) and where certain aspects for all practical purposes seem to behave according to some probability distribution. There are also applications governed by deterministic principles whose description is so complex or unwieldy that it makes sense to consider probabilistic approximations.

Every element of a graph dynamical system can be made stochastic in several ways. For example, in a sequential dynamical system the update sequence can be made stochastic. At each iteration step one may choose the update sequence w at random from a given distribution of update sequences with corresponding probabilities. The matching probability space of update sequences induces a probability space of SDS maps. A natural object to study in this regard is the <a href="Markov_chain" title="Markov chain">Markov chain</a> on state space induced by this collection of SDS maps. This case is referred to as update sequence stochastic GDS and is motivated by, e.g., processes where "events" occur at random according to certain rates (e.g. chemical reactions), synchronization in parallel computation/discrete event simulations, and in computational paradigms described later.

This specific example with stochastic update sequence illustrates two general facts for such systems: when passing to a stochastic graph dynamical system one is generally led to (1) a study of Markov chains (with specific structure governed by the constituents of the GDS), and (2) the resulting Markov chains tend to be large having an exponential number of states. A central goal in the study of stochastic GDS is to be able to derive reduced models.

One may also consider the case where the vertex functions are stochastic, i.e., function stochastic GDS. For example, Random <a href="Boolean_network" title="Boolean network">Boolean networks</a> are examples of function stochastic GDS using a synchronous update scheme and where the state space is K = {0, 1}. Finite <a href="Probabilistic_cellular_automata" class="mw-redirect" title="Probabilistic cellular automata">probabilistic cellular automata</a> (PCA) is another example of function stochastic GDS. In principle the class of Interacting particle systems (IPS) covers finite and infinite <a href="Probabilistic_cellular_automata" class="mw-redirect" title="Probabilistic cellular automata">PCA</a>, but in practice the work on IPS is largely concerned with the infinite case since this allows one to introduce more interesting topologies on state space.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Graph dynamical systems constitute a natural framework for capturing distributed systems such as biological networks and epidemics over social networks, many of which are frequently referred to as complex systems.

<ul><li><a href="Chemical_reaction_network_theory" title="Chemical reaction network theory">Chemical reaction network theory</a></li>

<li><a href="Dynamic_network_analysis" title="Dynamic network analysis">Dynamic network analysis</a> (a <a href="Social_science" title="Social science">social science</a> topic)</li>

<li><a href="Finite-state_machine" title="Finite-state machine">Finite-state machine</a></li>

<li><a href="Hopfield_network" title="Hopfield network">Hopfield network</a></li>

<li><a href="Petri_net" title="Petri net">Petri net</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="Wu:05" class="citation journal cs1">Wu, Chai Wah (2005). "Synchronization in networks of nonlinear dynamical systems coupled via a directed graph". Nonlinearity. 18 (3): 1057–1064. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005Nonli..18.1057W">2005Nonli..18.1057W</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1088%2F0951-7715%2F18%2F3%2F007">10.1088/0951-7715/18/3/007</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122111995">122111995</a>.</cite>

</li>

<li id="cite_note-Mortveit-08-2"><a href="#cite_ref-Mortveit-08_2-0">^</a> <cite id="Mortveit:08" class="citation book cs1">Mortveit, Henning S.; Reidys, Christian M. (2008). An introduction to sequential dynamical systems. Universitext. New York: <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-30654-4</bdi>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="Macauley:09a" class="citation journal cs1">Macauley, Matthew; Mortveit, Henning S. (2009). "Cycle equivalence of graph dynamical systems". Nonlinearity. 22 (2): 421–436. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0802.4412">0802.4412</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009Nonli..22..421M">2009Nonli..22..421M</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1088%2F0951-7715%2F22%2F2%2F010">10.1088/0951-7715/22/2/010</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17978550">17978550</a>.</cite></li>

<li><cite id="Golubitsky:03" class="citation book cs1"><a href="Marty_Golubitsky" title="Marty Golubitsky">Golubitsky, Martin</a>; Stewart, Ian (2003). The Symmetry Perspective. Basel: Birkhauser. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8176-2171-7</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20140903062024/http://www.samsi.info/sites/default/files/samsi-05-dec-08.pdf">Graph Dynamical Systems – A Mathematical Framework for Interaction-Based Systems, Their Analysis and Simulations by Henning Mortveit</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-26" href="https://en.wikipedia.org/wiki/?title=Graph_dynamical_system&oldid=1265271544">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>